class Solution {//leetcode873——最长斐波那契子数列的长度
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int>(n,2));
        unordered_map<int,int> hash;
        hash[arr[0]]=0;
        hash[arr[1]]=1;
        int ret=2;
        for(int i=2;i<n;i++){
            for(int j=1;j<i;j++){
                if(hash.count(arr[i]-arr[j])){
                    int k=hash[arr[i]-arr[j]];
                    if(k<j){
                        dp[j][i]=dp[k][j]+1;
                        ret=max(ret,dp[j][i]);
                    }
                }
            }
            hash[arr[i]]=i;
        }
        return ret<3?0:ret;
        
    }
};